package leetcode51_60;

import org.junit.Test;

import java.util.*;

/**
 * @author shhjiang_001
 * @create 2020-06-19 12:48
 */

       /*
        给出一个区间的集合，请合并所有重叠的区间。
        示例 1:
        输入: [[1,3],[2,6],[8,10],[15,18]]
        输出: [[1,6],[8,10],[15,18]]
        解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
        */


public class Solution56 {
    public int[][] merge1(int[][] intervals) {
        int length = intervals.length;
        if (length == 1 || length == 0) return intervals;
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        int newLength = length;
        for (int i = 0; i < length-1; i++) {
            if (intervals[i][1]>=intervals[i+1][0]){
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = Math.max(intervals[i][1],intervals[i+1][1]);
                intervals[i][0] = 0;
                intervals[i][1] = 0;
                newLength--;
            }
        }
        int[][] ints = new int[newLength][2];
        int index = 0;
        for (int i = 0; i < length; i++) {
            if (intervals[i][0]==0 && intervals[i][1] ==0){

            }else {
                ints[index][0] = intervals[i][0];
                ints[index][1] = intervals[i][1];
                index++;
            }
        }
        return ints;

    }
    public int[][] merge2(int[][] intervals) {
        int length = intervals.length;
        if (length == 0 || length == 1) return intervals;
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        ArrayList<int[]> list = new ArrayList<>();
        int index = 0;
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 0; i < length; i++) {
            if (i < length-1){
                if ( intervals[i+1][0] <= end){
                    // 这里要对end进行判定，或更新
                    end = Math.max(end,intervals[i+1][1]);
                }else {
                    list.add(new int[]{start,end});
                    start = intervals[i+1][0];
                    end = intervals[i+1][1];
                }
            }
            if (i == length-1){
                list.add(new int[]{start,end});
            }
        }
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public int[][] merge(int[][] intervals){
        Deque<int[]> deque = new ArrayDeque<>();
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        int x = intervals[0][0];
        int y = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            // 区间不相交
            if (intervals[i][0] > y){
                deque.add(new int[]{x,y});
                x = intervals[i][0];
                y = intervals[i][1];
            }else { // 区间相交
                y = Math.max(intervals[i][1],y);
            }
        }
        deque.add(new int[]{x,y});
        int[][] res = new int[deque.size()][];
        int i = 0;
        while (!deque.isEmpty()){
            res[i++] = deque.pop();
        }
        return res;
    }
    @Test
    public void test(){
        int[][] merge = merge(new int[][]{{2, 3}, {4, 5}, {6, 7}, {8, 9},{1,10}});
        merge.toString();
    }
}
